#include <stdio.h>

#define NUM 51
int p[NUM];
int m[NUM][NUM];
int s[NUM][NUM];

void MatrixChain(int n)
{
    for (int i = 1; i <= n; i++)
        m[i][i] = 0;                         // 当矩阵链长为1时，不计算计为0
    for (int r = 2; r <= n; r++)             // r表示矩阵链的长度即r个矩阵连乘
        for (int i = 1; i <= n - r + 1; i++) // i表示矩阵链的起始矩阵位置
        {
            int j = i + r - 1;                              // j表示矩阵链最后一个矩阵位置
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; // 初始化记录最少乘法次数的对应矩阵的元素
            s[i][j] = i;                                    // 初始化记录最优完全加括号位置的对应矩阵的元素
            for (int k = i + 1; k < j; k++)
            {                                                           // k表示最优完全加括号的位置，开始遍历所有情况
                int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; // 根据新的k计算新的乘法次数
                if (t < m[i][j])                                        // 当新的乘法次数少于之前的最少次数
                {
                    m[i][j] = t; // 更新最少乘法次数
                    s[i][j] = k; // 更新最优完全加括号的位置
                }
            }
        }
}

void TraceBack(int i, int j)
{
    // i == j 实际上就是经过递归矩阵链已经还原成了单个矩阵了
    // 此时不需要递归了，打印出结果即可
    if (i == j)
        printf("A%d", i);
    else
    {
        printf("(");
        TraceBack(i, s[i][j]);     // 先对前半部分进行递归
        TraceBack(s[i][j] + 1, j); // 再对后半部分进行递归
        printf(")");
    }
}

int main()
{
    int n;
    scanf("%d", &n); // 输入矩阵链长度
    int i, temp;
    // 根据原理保留矩阵关键数据
    for (i = 0; i < n; i++)
        scanf("%d%d", &p[i], &temp); // 相邻的两个能相乘的矩阵，前一个矩阵的列数等于后一个矩阵的行数
    p[n] = temp;                     // 只有最后一个矩阵的列数不会和之前的重复需要单独保存
    MatrixChain(n);                  // 调用动态规划算法，生成m与s数组
    printf("%d\n", m[1][n]);         // m[1][n]保存着整体最优值
    TraceBack(1, n);                 // 根据s数组记录的最优完全加括号的位置进行回溯，输出最优计算次序
                                     // (此回溯只是单纯的逆向整个序列与回溯算法不同)
    return 0;
}
